package com.qch.leecode.cyc2018.algorithm.a1_double_pointer;

import java.util.HashSet;
import java.util.Set;

/**
 * 算法思想：双指针：141. 环形链表
 * https://leetcode.cn/problems/linked-list-cycle/
 * <p>
 * 一开始看不懂题目,后来还是看不懂
 * 解题思路：
 * 1.步数1和2分别追击(快慢：龟兔赛跑)
 * 2、集合Set加不进去重复值
 *
 * 自己问题：
 * 看不懂题目，为空判断不准确
 *
 * @Author qch
 * @Date 2022/11/10
 * <p>
 *
 * 题目：
 * 给你一个链表的头节点 head ，判断链表中是否有环。
 * 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
 * 如果链表中存在环 ，则返回 true 。 否则，返回 false 。
 * <p>
 * 输入：head = [3,2,0,-4], pos = 1
 * 输出：true
 * 解释：链表中有一个环，其尾部连接到第二个节点。
 */
public class L6_Circle141 {
    public static void main(String[] args) {
        ListNode head = new ListNode(3);
        ListNode a = head;
        ListNode b = new ListNode(2);
        ListNode c = new ListNode(0);
        ListNode d = new ListNode(-4);
        a.next = b;
        b.next = c;
        c.next = d;
        d.next = b;
        boolean flag = official_set_good_hasCycle(a);
        System.out.println(flag);

    }

    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    /**
     * 解法一：龟兔赛跑
     * @param head
     * @return
     */
    public static boolean official_good_hasCycle(ListNode head) {
        if (head == null||head.next==null) {
            return false;
        }
        ListNode slow = head;
        ListNode fast = head.next;
        while (slow!=fast)
        {
           /**
             *  if(slow==null||fast=null)
            *  1.fast.next为空一定要考虑，否则fast.next.next会出现空指针
            *  2.要考虑fast是否为空，否则不是slow是否为空
            *
            */
            if(fast==null||fast.next==null)
            {return false;}
            slow=slow.next;
            //fast=fast.next会变成死循环，一定要保持两步
            fast=fast.next.next;
        }
        return true;
    }

    /**
     * 解法二：集合遍历(逊色法一)
     * @param head
     * @return
     */
    public static boolean official_set_good_hasCycle(ListNode head) {
        Set<ListNode>set=new HashSet<>();
        ListNode p=head;
        while (p!=null)
        {
            //加入集合不成功则有环，因为相同的节点加不进去
           if( !set.add(p))
           {
               return true;
           }
           p=p.next;
        }
        return false;
    }

    /**
     * 解法一的不同写法
     * @param head
     * @return
     */
    public static boolean cyc2018_hasCycle(ListNode head) {
        if (head == null) {
            return false;
        }
        ListNode l1 = head, l2 = head.next;
        while (l1 != null && l2 != null && l2.next != null) {
            if (l1 == l2) {
                return true;
            }
            l1 = l1.next;
            l2 = l2.next.next;
        }
        return false;
    }

    /**
     * 21 / 23
     * [1] ,-1 未通过
     *
     * @param head
     * @return
     */
    public static boolean error_own_hasCycle(ListNode head) {
        ListNode a = head;
        ListNode b = head;
        if (a == null)
            return false;
        while (a != null && b != null) {
            a = a.next;
            b = b.next;
            if (b != null) {
                b = b.next;
            }
            if (a == b) {
                return true;
            }
        }
        return false;
    }
}
